package com.cet.algorithm.二叉树.将二叉搜索树转化为累加树;

import com.cet.algorithm.test.二叉树.TreeNode;
import com.cet.algorithm.test.二叉树.TreeOperation;

/**
 * @program: cet-practice
 * @description: 将二叉搜索树转化为累加树
 * @author: 陈恩涛
 * @create: 2023-05-26 11:44
 **/
public class LC538 {

    int sum = 0;

    /**
     * 二叉搜索树中序遍历为升序数组，那么变体 right root left为倒序数组，依次遍历累加即可
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {
        convertSumTree(root);
        return root;
    }

    public void convertSumTree(TreeNode root) {
        if (root == null) {
            return;
        }

        // right
        if (root.right != null) {
            convertSumTree(root.right);
        }

        // root
        sum += root.val;
        root.val = sum;
        // left
        if (root.left != null) {
            convertSumTree(root.left);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4, new TreeNode(1, new TreeNode(0), new TreeNode(2, null, new TreeNode(3))), new TreeNode(6, new TreeNode(5), new TreeNode(7, null, new TreeNode(8))));
        LC538 lc538 = new LC538();
        lc538.convertBST(root);
        TreeOperation.show(root);
    }
}
